Problem:
A recursive descent parser (RDP) is a top-down parser built from a set of grammer rules. It uses recursive procedure to identify the input string tokens, basically RDP parses the tokens from left to right, such that it does not require backtracking, therefore it is not allowed to have any immediate left recursion and indirect left recursion. Such parsing in RDP is possible only for the class of LL(k) grammars, which are the context-free grammars that exclude all ambiguous grammars, like the grammars containing left recursion. Every context-free grammars must be able to be transformed into an equivalent grammar without left recursion. Because of the top-down (left-to-right) approach without backtracking, the RDP runs in linear time.
There are some restrictions for the grammars of RDP:
1. Grammer must be deterministic, i.e. each token must follow exactly 1 grammer, but not more.
2. No left recursion is allowed, i.e. the leftmost symbol must be a terminal symbol.
Example of context-free grammar transformation:
The following expression with left recursion
expr -> term | expr + term | expr - term
can be rewritten to be
Expression 1 (without left recursion):
expr -> term { + term | - term }
OR
Expression 2 (without left recursion):
expr -> term exprRest
exprRest -> + term exprRest | - term exprRest | $
|
Application of RDP:
Because of such high performance of RDP, traditionally the programming compilers are built from the RDPs. The compilers try to read the high-level source code as a number of string tokens, and parse them one-by-one in a top-down way, and then translate them to be corresponding low-level mWachine code, such actions can be done by using RDPs.
|